package leetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class LeetCode_day10 {
	
	/**
	 * Merge all overlapping intervals.
	 * 
	 * First sort the intervals according to starting time.
	 * 
	 * In the sorted array of intervals, if interval[i] doesn't overlap with
	 * interval[i-1], then interval[i+1] cannot overlap with interval[i-1]
	 * 
	 * 1. Sort the intervals based on increasing order of starting time.
	 * 2. Push the first interval on to a stack.
	 * 3. For each interval do the following
	 * ……..a. If the current interval does not overlap with the stack top, push it.
	 * ……..b. If the current interval overlaps with stack top and ending time of 
	 * current interval is more than that of stack top, update stack top with the ending
	 *  time of current interval.
	 * 4. At the end stack contains the merged intervals.
	 * 
	 * @param intervals
	 */
	public static void mergeIntervals(Interval[] intervals){
		if(intervals == null) return;
		List<Interval> newIntervals = new ArrayList<Interval>();
		Arrays.sort(intervals);
		Interval pre = intervals[0];
		for(int i = 1 ; i < intervals.length ; i++){
			if(intervals[i].begin <= pre.end){//merge
				if(intervals[i].end > pre.end)
					pre.end = intervals[i].end;
			}else{//cannot merge
				newIntervals.add(pre);
				pre = intervals[i];
			}
		}
		newIntervals.add(pre);
		
		for(Interval inter : newIntervals)
			System.out.println("["+inter.begin+","+inter.end+"]");
	}
	
	public static void insertInterval(Interval[] intervals, Interval newInterval){
		if(intervals == null || newInterval == null) return;
		
		List<Interval> inters;// = new ArrayList<Interval>();
		int[] inds = new int[2];
		//left
		for(int i = 0 ; i < intervals.length ; i++){
			if(intervals[i].end > newInterval.begin) {
				inds[0] = i;
				break;
			}
		}
		//right
		for(int i = intervals.length - 1 ; i >= 0 ; i++)
			if(intervals[i].begin < newInterval.end) {
				inds[1] = i;
				break;
			}
		//check merge
		if(inds[0] == inds[1]){
			intervals[inds[0]].begin = newInterval.begin;
			intervals[inds[0]].end = newInterval.end;
			inters = Arrays.asList(intervals);
		}else{
			inters = new ArrayList<Interval>();
			for(int i = 0 ; i < inds[0] ; i++) inters.add(intervals[i]);
			
			for(int i = inds[0] ; i<= inds[1] ; i++){
				if(newInterval.begin >= intervals[i].begin && newInterval.begin <= intervals[i].end
						|| newInterval.begin <= intervals[i].begin && newInterval.end >= intervals[i].begin){//merge
					newInterval.begin = Math.min(newInterval.begin, intervals[i].begin);
					newInterval.end = Math.max(newInterval.end, intervals[i].end);
					inters.add(newInterval);
				}else if(intervals[i].end < newInterval.begin) inters.add(intervals[i]);
				else if(intervals[i].begin > newInterval.end){
					inters.add(newInterval);
					inters.add(intervals[i]);
				}
			}
			
			for(int i = inds[1]+1 ; i < intervals.length ; i++) inters.add(intervals[i]);
			for(Interval ints : inters)
				System.out.println("["+ints.begin+","+ints.end+"]");
		}
	}
	
	public static void insertIntervalOpt(Interval[] intervals, Interval newInterval){
		if(intervals == null || newInterval == null) return;
		List<Interval> newInters = new ArrayList<Interval>();
		for(int i = 0 ; i < intervals.length ; i++){
			if(intervals[i].end < newInterval.end){
				newInters.add(intervals[i]);
				continue;
			}else if(intervals[i].begin > newInterval.begin){
				newInters.add(intervals[i]);
			}else{
				newInterval.begin = Math.min(newInterval.begin, intervals[i].begin);
				newInterval.end = Math.max(newInterval.end, intervals[i].end);
				newInters.add(newInterval);
			}
		}
		for(Interval ints : newInters)
			System.out.println("["+ints.begin+","+ints.end+"]");
	}
	
	public static void lengthOfLastWord(String str){
		if(str == null) return;
		String[] strs = str.split(" ");
		if(strs.length > 1)
			System.out.println("Last word length is: "+strs[strs.length-1].length());
		else System.out.println("No last word.");
	}
	
	public static void spiralMatrixII(int n){
		int[][] matrix = new int[n][n];
		int layer = (n+1)/2;
		int count = 1, total = n*n;
		for(int i = 0 ; i < layer ; i++){
			//up
			for(int j = i ; j <= n-1-i ; j++)
				if(count <= total)
					matrix[i][j] = count++;
			//right
			for(int j = i+1 ; j <= n-2-i ; j++)
				if(count <= total)
					matrix[j][n-1-i] = count++;
			//down
			for(int j = n-1-i ; j >= i ; j--)
				if(count <= total)
					matrix[n-1-i][j] = count++;
			//left
			for(int j = n-2-i ; j >= i+1 ; j--)
				if(count <= total)
					matrix[j][i] = count++;
		}
		for(int i = 0 ; i < n ; i++){
			System.out.println();
			for(int j = 0 ; j < n ; j++){
				System.out.print(matrix[i][j] + " ");
			}
		}
	}

	public static void permutationSequence(int n, int k){
		int[] preper = new int[n], res = new int[n];
		for(int i = 0 ; i < n ; i++) {
			preper[i] = i+1;
			res[i] = i+1;
		}
		for(int i = 1 ; i < k ; i++){
			//get next permutation
			int ind = -1;
			for(int j = n-1 ; j >= 0 ; j--){
				if(res[j-1] < res[j]){
					ind = j-1;
					break;
				}
			}
			if(ind == -1) {
				res = preper.clone();
				continue;
			}
			else{
				int ind2 = -1;
				for(int j = n-1 ; j >= 0 ; j--)
					if(res[j] > res[ind]) {
						ind2 = j;
						break;
					}
				//swap
				res[ind] = res[ind] ^ res[ind2];
				res[ind2] = res[ind] ^ res[ind2];
				res[ind] = res[ind] ^ res[ind2];
				
				//reverse
				Stack<Integer> s = new Stack<Integer>();
				for(int j = ind+1 ; j < res.length ; j++) s.push(res[j]);
				for(int j = ind+1 ; j < res.length ; j++) res[j] = s.pop();
			}
		}
		
		System.out.println();
		for(int i = 0 ; i < res.length ; i++)
			System.out.print(res[i] + " ");
	}
	
	public static void rotateList(ListNode head, int k){
		if(head == null) return;
		
		//make the linked list to be circular
		ListNode tail = head;
		int length = 1;
		while(tail.next != null) {
			length++;
			tail = tail.next;
		}
		tail.next = head;
		//find new head
		ListNode newhead = head;
		ListNode newtail = head;
		for(int i = 1 ; i < length-k+1 ; i++){
			newtail = newhead;
			newhead = newhead.next;
		}
		newtail.next = null;
		
		ListNode ind = newhead;
		System.out.print(ind.val + " ");
		while(ind.next != null){
			ind = ind.next;
			System.out.print(ind.val + " ");
		}
	}
	
	public static void uniquePaths(int m , int n){
		List<List<Interval>> ress = new ArrayList<List<Interval>>();
		Interval startPos = new Interval(1,1);
		Interval endPos = new Interval(m, n);
		List<Interval> curPath = new ArrayList<Interval>();
		uniquePathsDFS(ress, startPos, endPos, curPath);
		
		System.out.println();
		System.out.println("There are " + ress.size() + " unique pathes.");
	}
	
	public static void uniquePathsDFS(List<List<Interval>> ress, Interval curPos, Interval tar, List<Interval> curPath){
		if(curPos.begin  == tar.begin && curPos.end == tar.end) {
			ress.add(curPath);
			return;
		}else if(curPos.begin > tar.begin || curPos.end > tar.end) return;
		else{
			curPath.add(curPos);
			List<Interval> path1 = new ArrayList<Interval>();
			path1.addAll(curPath);
			uniquePathsDFS(ress, new Interval(curPos.begin + 1, curPos.end), tar, path1);
			
			List<Interval> path2 = new ArrayList<Interval>();
			path2.addAll(curPath);

			uniquePathsDFS(ress, new Interval(curPos.begin, curPos.end + 1), tar, path2);
		}
	}
	
	public static void uniquePathsII(int[][] matrix){
		List<List<Interval>> ress = new ArrayList<List<Interval>>();
		Interval startPos = new Interval(1,1);
		Interval endPos = new Interval(matrix.length, matrix[0].length);
		List<Interval> curPath = new ArrayList<Interval>();
		uniquePathsDFSII(ress, startPos, endPos, curPath, matrix);
		
		System.out.println();
		System.out.println("There are " + ress.size() + " unique pathes.");
	}
	
	public static void uniquePathsDFSII(List<List<Interval>> ress, Interval curPos, Interval tar, List<Interval> curPath, int[][] matrix){
		if(curPos.begin  == tar.begin && curPos.end == tar.end) {
			ress.add(curPath);
			return;
		}else if(curPos.begin > tar.begin || curPos.end > tar.end || matrix[curPos.begin][curPos.end] == 1) return;
		else{
			curPath.add(curPos);
			List<Interval> path1 = new ArrayList<Interval>();
			path1.addAll(curPath);
			uniquePathsDFSII(ress, new Interval(curPos.begin + 1, curPos.end), tar, path1, matrix);
			
			List<Interval> path2 = new ArrayList<Interval>();
			path2.addAll(curPath);

			uniquePathsDFSII(ress, new Interval(curPos.begin, curPos.end + 1), tar, path2, matrix);
		}
	}
	
	/**
	 * ! It's a typical dynamic programming problem
	 * cost[0][i] = cost[0][i-1] + grid[0][i]
	 * cost[i][0] = cost[i-1][0] + grid[i][0]
	 * cost[i][j] = min(a[i-1][j], a[i][j-1]) + grid[i][j]
	 * 如果是一排一排地扫，我们只需要上一排的数据
	 * 如果是一列一列地扫，我们只需要上一列的数据
	 * 因此可以使用滚动数组
	 * 
	 * 
	 * Given a m x n grid filled with non-negative numbers, 
	 * find a path from top left to bottom right which minimizes the 
	 * sum of all numbers along its path.
	 * Note: You can only move either down or right at any point in time.
	 * @param grid
	 */
	public static void minimumPathSum(int[][] grid){
		if(grid == null) return;
		int m = grid.length, n = grid[0].length;
		int[] cost = new int[n+1];
		Arrays.fill(cost, Integer.MAX_VALUE);
		cost[1] = 0;
		for(int i = 0 ; i < m ; i++){
			for(int j = 0 ; j < n ; j++)
				cost[j+1] = Math.min(cost[j+1], cost[j]) + grid[i][j];
				//here, cost[j+1] is the upper side, cost[j] is the left side
		}
		System.out.println();
		System.out.println("The minimum cost is: " + cost[n]);
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Interval[] intervals = new Interval[4];
		intervals[0] = new Interval(1,3);
		intervals[1] = new Interval(2,6);
		intervals[2] = new Interval(8,10);
		intervals[3] = new Interval(15,18);
		mergeIntervals(intervals);
		permutationSequence(3,3);
		System.out.println();
		spiralMatrixII(4);
		
		System.out.println();
		ListNode head = new ListNode(1);
		head.next = new ListNode(2); head.next.next = new ListNode(3);
		head.next.next.next = new ListNode(4);head.next.next.next.next = new ListNode(5);
		rotateList(head, 2);
		uniquePaths(4,3);
		int[][] grid = new int[3][4];
		grid[0] = new int[]{1,2,2,3};
		grid[1] = new int[]{4,7,5,3};
		grid[2] = new int[]{2,1,0,5};
		minimumPathSum(grid);
	}

}
class Interval implements Comparable<Interval>, Cloneable{
	public int begin, end;

	public Interval(int begin, int end){
		this.begin = begin;
		this.end = end;
	}
	@Override
	public int compareTo(Interval i) {
		return begin - i.begin;
	}
}


